Міністерство освіти і науки України
Національний університет "Львівська політехніка"
Кафедра маркетингу і логістики
Лабораторна робота №3 (частина 2)
З курсу «Економіко-математичні методи і моделі»
(варіант № 19)
ЛАБОРАТОРНА РОБОТА №3
ПОБУДОВА ЛІНІЙНОЇ МОДЕЛІ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ
ТА ЇЇ АНАЛІЗ
І. Загальні положення
Загальною формою задачі лінійного програмування є задача на знаходження екстремуму (мінімуму чи максимуму) лінійної цільової функції при лінійній системі обмежень, що включає як рівності, так і нерівності обох знаків, і при невідомих змінних, з яких одні пов’язані умовою невід’ємності, другі – умовою недодатності, а на знак третіх ніяких умов не накладено.
ІІ. Теоретичні відомості
За допомогою задачі лінійного програмування можна вирішити багато задач оптимізації, зокрема задачу про раціональне використання наявних ресурсів. У загальному вигляді задача може бути сформульована таким чином.
Припустимо, підприємство може випускати n видів продукції, використовуючи m видів ресурсів. При цьому відомі запаси кожного і-того виду ресурсу (), витрати кожного виду ресурсу на випуск кожного j-го виду продукції () та прибуток, що отримується з одиниці випущеної продукції (). Мета задачі полягає у тому, щоб скласти такий план виробництва продукції (), при якому отриманий підприємством прибуток від виробництва Z був би найбільшим.
Отже, математична модель задачі полягає в тому, щоб знайти виробничу програму, що максимізує цільову функцію:
. (3.1)
При цьому, яка б не була виробнича програма, її компоненти повинні задовольняти умові, що сумарне використання кожного виду ресурсу при виробництві всіх видів продукції не повинно перевищувати наявну кількість даного виду ресурсу, тобто
; (3.2)
. (3.3)
На значення можуть бути додатково накладені обмеження стосовно обсягів виробництва:
; (3.4)
. (3.5)
При цьому, оскільки компоненти виробничої програми – кількість виробів, то вони не можуть бути виражені від’ємними значеннями:
. (3.6)
Для аналізу стійкості важливим є діапазон зміни параметрів, в яких оптимальне рішення залишається оптимальним. У процесі пошуку оптимального рішення можна отримати так званий звіт про стійкість, у якому містяться межі коефіцієнтів цільової функції. Зміна коефіцієнтів в цих межах не призводить до зміни оптимального рішення. Аналогічні інтервали встановлюються для запасів ресурсів. При виході за визначені межі стійкості оптимальне рішення може мінятися як за номенклатурою продукції, що випускається, так і за обсягами випуску (без зміни номенклатури).
Двоїстою до основної задачі (3.1) – (3.6) називається така задача: знайти сукупність значень y1, y2,…, ym, для яких функція:
(3.7)
досягає мінімуму і задовольняє систему нерівностей:
; (3.8)
; (3.9)
. (3.10)
Багато задач лінійного програмування ставляться у вигляді основної або двоїстої задачі, тому є сенс говорити про пару двоїстих задач лінійного програмування.
Якщо одна з пари двоїстих задач має розв’язок (тобто оптимальний план), то і друга – обов’язково має розв’язок, причому:
max Z = min W. (3.11)
Для побудови двоїстої задачі необхідно основну задачу звести до стандартного вигляду, враховуючи тип екстремуму цільової функції.
Побудова двоїстої задачі до основної здійснюється в послідовності:
І. Стандартизація основної задачі:
1) у всіх обмеженнях вільні члени розміщені в правій частині рівності (нерівності), а члени з невідомим – у лівій;
2) усі обмеження нерівності основної задачі мають бути записані так, щоб знаки нерівності у них були спрямовані в один і той самий бі...
